package chart.图的存储;

import java.util.*;

/**
 * 邻接矩阵
 * <p>有 n 个顶点, 建立 n * n 的二维数组, matrix[i][j] 表示 i 到 j 的边</p>
 * <p>适用于存储稠密图, 稠密图边多, 而邻接矩阵的大小只受顶点数量的影响</p>
 *
 * @author yezh
 * @date 2023/7/10 15:24
 */
public class AdjacencyMatrix extends AbstractGraph {

    public static void main(String[] args) {
        AdjacencyMatrix undirectedGraph = new AdjacencyMatrix(4, false);
        Edge e1 = new Edge(0, 1);
        Edge e2 = new Edge(0, 2);
        Edge e4 = new Edge(1, 2);
        Edge e3 = new Edge(1, 3);
        Edge e5 = new Edge(2, 3);
        List<Edge> edges = Arrays.asList(e1, e2, e3, e4, e5);
        undirectedGraph.createGraph(edges);
        undirectedGraph.print();
        System.out.println();
        System.out.println(undirectedGraph.getNeighborVertex(0));
        System.out.println(undirectedGraph.getNeighborVertex(1));
        System.out.println(undirectedGraph.getNeighborVertex(2));
        System.out.println(undirectedGraph.getNeighborVertex(3));
    }

    public static final int INFINITY = Integer.MAX_VALUE;

    private final int[][] matrix;

    public AdjacencyMatrix(int v, boolean directed) {
        super(v, directed);
        this.matrix = new int[v][v];
        for (int i = 0; i < v; i++) Arrays.fill(matrix[i], INFINITY);
    }

    @Override
    public void createGraph(List<Edge> edges) {
        if (directed) for (Edge edge : edges) this.matrix[edge.getArcTail()][edge.getArcHead()] = edge.getWeigh();
        else {
            for (Edge edge : edges) {
                this.matrix[edge.getArcTail()][edge.getArcHead()] = edge.getWeigh();
                this.matrix[edge.getArcHead()][edge.getArcTail()] = edge.getWeigh();
            }
        }
    }

    @Override
    public List<Integer> getNeighborVertex(int vertex) {
        // 时间复杂度 O(n)
        List<Integer> res = new ArrayList<>(matrix.length);
        for (int i = 0; i < v; i++) if (isEfficientEdge(matrix[vertex][i])) res.add(i);
        return res;
    }

    @Override
    public List<Edge> getNeighborEdge(int vertex) {
        List<Edge> res = new ArrayList<>(v);
        for (int i = 0; i < v; i++)
            if (isEfficientEdge(matrix[vertex][i])) res.add(new Edge(vertex, i, matrix[vertex][i]));
        return res;
    }

    @Override
    public List<Edge> allEdge() {
        List<Edge> edges = new ArrayList<>(v);
        for (int i = 0; i < v; i++)
            for (int j = 0; j < v; j++)
                if (isEfficientEdge(matrix[i][j])) edges.add(new Edge(i, j, matrix[i][j]));
        return edges;
    }

    @Override
    public void print() {
        for (int i = 0; i < v; i++) System.out.println(Arrays.toString(matrix[i]));
    }

    private boolean isEfficientEdge(int i) {
        return i != INFINITY;
    }

}
